package com.dycong.common.leetcode;

import com.dycong.common.leetcode.ds.tree.TreeNode;

import java.util.Stack;

/**
 * 二叉树转链表(快手)
 * 这是Leetcode 114题。
 * 给定一个二叉树，原地将它展开为链表。
 * <p>
 * 例如，给定二叉树
 * <p>
 * <p>
 * 1
 * / \
 * 2   5
 * / \   \
 * 3   4   6
 * 将其展开为：
 * <p>
 * 1
 * \
 * 2
 * \
 * 3
 * \
 * 4
 * \
 * 5
 * \
 * 6
 * 这道题目的关键是转换的时候递归的时候记住是先转换右子树，再转换左子树。
 * 所以需要记录一下右子树转换完之后链表的头结点在哪里。注意没有新定义一个next指针，而是直接将right 当做next指针,那么Left指针我们赋值成null就可以了。
 *
 * @author dycong
 * @date 2019/10/12 9:26
 */
public class TreeFlatten_114 {

    public void flatten(TreeNode root) {
        if (null == root) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (null != cur.right) stack.push(cur.right);
            if (null != cur.left) stack.push(cur.left);

            if (!stack.isEmpty()) cur.right = stack.peek();
            cur.left = null;
        }
    }

    //暂存上一个处理的节点
    private TreeNode prev = null;

    //倒着添加链表呀
    public void flatten2(TreeNode root) {
        if (root == null)  return;
        flatten2(root.right); // 先转换右子树
        flatten2(root.left);
        root.right = prev;  // 右子树指向链表的头
        root.left = null; // 把左子树置空
        prev = root; // 当前结点为链表头
    }
}
